package airthmetic.exercise.dp;

import java.util.Arrays;

public class _516_最长回文子序列 {
    public static int longestPalindromeSubseq(String s) {
        /**
         1. 确定状态参数和选择决策
         状态参数：是子问题与原问题之间变化的值
         此题为：s字符串的左边界i 与右边界的j
         选择/决策：做选择使状态参数变化并趋近于原问题的解
         此题为；再i与j之间循环做选择
         2. 定义dp数组(dp table)的含义 子问题的解需要缓存起来 动态规划的思想是：根据子问题的解推导原问题
         此题为：int[][] dp = new int[][]; 即：dp[0][n-1]是整个字符串的最大子序列的字符个数
         3. 初始化dp数组
         i与j是字符串的左右边界 所以i和j重叠的位置必然是回文子序列所以为1
         因此我们初始化
         for(int i=0; i<n;i++){
         dp[i][i] = 1;
         }
         还有我们知道一个一直条件，即i>j时是不成立的子序列
         所以只有i==j || i<j时才成立,因为java初始化一个int数组默认就为0所以不需要处理
         4. 推导状态转移逻辑 (状态转移公式)
         if(s[i] != s[j]){
         dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
         }else{
         dp[i][j] = dp[i+1][j-1] + 2;
         }
         */
        char[] cs = s.toCharArray();
        int n = cs.length;
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
        }
        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(cs[i] != cs[j]){
                    dp[i][j] = Math.max(dp[i][j-1], dp[i+1][j]);
                }else{
                    dp[i][j] = dp[i+1][j-1] + 2;
                }
            }
        }

        return dp[0][n-1];

    }


    public static int longestPalindromeSubseq2(String s) {
        /**

         1.确定状态参数和选择
         状态参数：状态参数是在原问题与子问题之间不断变化的值。
         思考原问题与子问题：
         原问题：s = "bbbab"
         子问题: s = "bbba"
         所以此题有两个状态参数，分别为i,j。子序列的左右边界

         选择/决策：
         做选择使状态参数不断变化并趋近于原问题的解。
         这里就是选择i,j的边界

         2.定义dp table的含义
         int[][] dp = new int[][];
         dp[i][j]表示当前回文子序列的长度

         3.初始化dp table
         根据题意分析：
         如果i>j不能是一个字符串。所以i>j 都是0
         i==j 都是1 因为一个字符是特殊的回文子序列
         所以：
         for(int i=0; i<n; i++){
         dp[i][i] = 1;
         }

         4.推导状态转移公式
         回到子序列的定义上：
         如果两个边界相等，那么是可以根据当前序列的子问题(dp[i+1]			[j-1]) + 2得到当前序列长度
         如果两个边界不相等，那么有两种情况:
         dp[i,j-1] 和 dp[i+1,j]

         所以公式为：
         if(sc[i] == sc[j]){
         dp[i][j] = dp[i+1][j-1] + 2;
         }else{
         dp[i][j] = Math.max(dp[i,j-1], dp[i+1,j]);
         }


         注意：
         因为分析得知，如果sc[i] != sc[j] 需要从dp[i,j-1], dp[i+1,j]转移过来，所以不能是i从0到n-1遍历。应该是,i从n-1到0。j从i+1到n;
         */

        char[] sc = s.toCharArray();
        int n = sc.length;
        int[][] dp = new int[n][n];
        for(int i=0; i<n; i++){
            dp[i][i] = 1;
        }

        for(int i=n-1; i>=0; i--){
            for(int j=i+1; j<n; j++){
                if(sc[i] == sc[j]){
                    dp[i][j] = dp[i+1][j-1] + 2;
                }else{
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
                }
            }
        }

        return dp[0][n-1];
    }


    public static void main(String[] args) {
        System.out.println(longestPalindromeSubseq("bbbab"));
        System.out.println(longestPalindromeSubseq("cbbd"));

        int[] coins = new int[]{3,5,13,2,1};
        Arrays.sort(coins);
        int n = (coins.length - 1) >> 1;
        for(int i=0; i< n; i++){
            int temp = coins[i];
            coins[i] = coins[coins.length - 1 - i];
            coins[coins.length - 1 -i] = temp;
        }

        System.out.println(coins);

        System.out.println(5*0);
    }
}
